package com.haidechizi.leetcode;


/**
 * 给定一个二叉树，原地将它展开为链表。
 * <p>
 * 例如，给定二叉树
 * <p>
 * 1
 * / \
 * 2   5
 * / \   \
 * 3   4   6
 * 将其展开为：
 * <p>
 * 1
 * \
 * 2
 * \
 * 3
 * \
 * 4
 * \
 * 5
 * \
 * 6
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _114_二叉树展开为链表 {

    /**
     * 利用二叉树的前序遍历
     *
     * @param root
     */


    public void flatten(TreeNode root) {
        TreeNode target = root;
        while (target != null) {
            TreeNode oldRight = target.right;
            target.right = target.left;
            target.left = null;
            TreeNode rightMost = target;
            while (rightMost.right != null) {
                rightMost = rightMost.right;
            }
            rightMost.right = oldRight;
            target = target.right;
        }
    }

    public void flatten1(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode oldRight = root.right;
        root.right = root.left;
        root.left = null;
        TreeNode rightMost = root;
        while (rightMost.right != null) {
            rightMost = rightMost.right;
        }
        rightMost.right = oldRight;
        flatten(root.right);

    }


    /*public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode oldRight = root.right;
        root.right = root.left;
        root.left = null;
        TreeNode rightMost = root;
        while (rightMost.right != null) {
            rightMost = rightMost.right;
        }
        rightMost.right = oldRight;
        flatten(root.right);

    }*/

}
